The present invention relates to data telecommunications in general, and more particularly to forward error correction therefor.
The use of Forward Error Correction (FEC) techniques in the design of digital communications and storage systems is well known. FEC is used to find and correct limited errors caused by a transport or storage system in order to ensure the validity of the received message without requiring retransmissions. In general, FEC encoding techniques, such as Reed-Solomon (RS) encoding, provide data redundancy by adding extra code symbols to a transmitted message which provide the necessary detection and correction information. The number of redundant symbols is determined by the amount and type of error correction required. RS encoding is an example of a block code where the data to be transmitted are divided into blocks, with each block comprising k symbols of data. An additional r redundancy symbols are then added to each block of k data symbols to form a code word of length n=k+r. The xe2x80x9ccode ratexe2x80x9d of the code refers to the ratio k/n, and is used to express the average amount of data symbols versus the amount of transmitted symbols. Thus, a code rate of 0.8 would indicate that the average over all time intervals T of the ratio of data symbols that were encoded in time interval T to the total number of transmitted symbols in time interval T, is 80%.
In general, the additional redundancy symbols must contain enough information to allow the position of an erroneous information symbol to be located and its value determined. For example, an RS decoder can detect and correct up to r/2 incorrect symbols if there are (r=nxe2x88x92k) redundant symbols in each code word, as one redundant symbol is used to detect and locate each error, and one more redundant symbol is used to identify the precise value of that error. Some symbols that are either known or suspected to be in error or otherwise unreliable may be labeled as xe2x80x9cerasures.xe2x80x9d The position of each erasure may be provided in advance to the decoder which then ignores the actual value of the erasure and instead reconstructs its value using the redundancy symbols. Since the position of each erasure is known, only one redundant symbol is needed to reconstruct the value of an erasure, and an additional redundant symbol to determine the location of the erasure is not required. In general, if a code word contains E symbols that are erasures whose locations are known and e symbols that are errors with unknown locations, the code word can be correctly decoded provided that (2e+E) less than r. If the locations of all the errors are known to the decoder, the message can be correctly decoded provided that E less than r, thus requiring half the number of redundant symbols needed to correct errors whose locations are not known.
While conventional FEC techniques may be used more or less successfully to correct errors, they generally must be designed with a redundancy that is greater than the number of errors they are expected to correct, with RS codes requiring up to twice as many redundancy symbols as error symbols. Thus, the greater the redundancy, the less room there is for data in each code word and the less throughput of the communication channel due to error correction overhead.
In one aspect of the present invention a forward error correction system is provided including a coder operative to encode a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, at least one transmitting modem for transmitting the code words, at least one receiving modem for receiving the code words, a decoder operative to detect errors in any of the code words, correct any of the errors and erasures in the code words, and communicate the positions of any of the errors, and a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions to the decoder.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the coder is a Reed-Solomon coder.
In another aspect of the present invention the code words are either of systematic, non-systematic, and convolutional code words.
In another aspect of the present invention the code words are of different lengths.
In another aspect of the present invention the at least one transmitting modem includes a plurality of transmitting modems, and the system further includes a demultiplexer for demultiplexing the code words, thereby causing each of the transmitting modems to transmit a different portion of each of the code words.
In another aspect of the present invention the at least one receiving modem includes a plurality of receiving modems for receiving the different portions of each of the code words, and the system further includes a multiplexer for multiplexing the portions, thereby reconstructing the code words.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the system further includes an interleaver for interleaving the code words, and a deinterleaver for deinterleaving the interleaved code words.
In another aspect of the present invention the controller is operative to send a configuration signal to the decoder configuring the decoder for decoding either of the primary and the secondary code words.
In another aspect of the present invention a forward error correction system is provided including a coder operative to encode a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, a demultiplexer for demultiplexing each of the code words into a plurality of portions, a plurality of transmitting modems, each transmitting modem for transmitting a different one of the plurality of portions, a plurality of receiving modems for receiving the plurality of portions, a multiplexer for multiplexing the plurality of portions, thereby reconstructing the code words, a primary decoder operative to detect any errors in any of the primary code words, correct any of the errors, and communicate the positions of any of the errors, a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions, a secondary decoder operative to receive the report of erasure positions and correct any of the erasures in the secondary code words.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the coder is a Reed-Solomon coder.
In another aspect of the present invention the code words are either of systematic, non-systematic, and convolutional code words.
In another aspect of the present invention the code words are of different lengths.
In another aspect of the present invention the system further includes an interleaver for interleaving the code words, and a deinterleaver for deinterleaving the interleaved code words.
In another aspect of the present invention a forward error correction system is provided including a coder operative to encode a data stream into at least one code word at a first code rate, a demultiplexer for demultiplexing the code word into a plurality of portions, a plurality of transmitting modems, each transmitting modem for transmitting a different one of the plurality of portions, a plurality of receiving modems for receiving the plurality of portions, where any of the modems is operative to determine its function status and transmit a signal indicating the status, a multiplexer for multiplexing the plurality of portions, thereby reconstructing the code word, a decoder operative to detect any errors in the code word, correct any of the errors, and correct erasures, and a controller operative to receive the signal and, where the signal indicates that any of the modems is functioning improperly, report erasure positions corresponding to the portion transmitted by the improperly functioning modem to the decoder, where the decoder is operative to receive the report of erasure positions and correct any of the erasures in any of the code words.
In another aspect of the present invention the controller is operative to instruct either of the encoder and the decoder to encode at a second code rate having a sufficient redundancy to accommodate the number of the errors and erasures.
In another aspect of the present invention a forward error correction system is provided including an outer coder operative to encode a data stream into at least one outer code word, an inner coder operative to encode the outer code word into at least one inner code word using either of an error correcting code and an error checking code, a communications channel for transmitting the inner code word, an inner decoder operative to receive the transmitted inner code word from the communications channel, determine the validity of the inner code word, communicate the validity of the inner code word, and decode the inner code word, thereby reconstituting the outer code word, a controller operative to receive from the inner coder the communication of validity of the inner code word, map the inner code word to its corresponding position in the reconstituted outer code word, and, where the inner code word is invalid, and report the position as an erasure position, and an outer decoder operative to receive the reconstituted outer code word from the inner decoder and the erasure positions from the inner decoder, detect errors in the reconstituted outer code word, and correct any of the errors and erasures in the reconstituted outer code word.
In another aspect of the present invention the outer coder is a Reed-Solomon coder and the outer decoder is a Reed-Solomon decoder.
In another aspect of the present invention the inner coder and the inner decoder employ Trellis Coded Modulation.
In another aspect of the present invention the inner coder and the inner decoder employ Cyclic Redundancy Checking.
In another aspect of the present invention the system further includes an interleaver for interleaving the code words, and a deinterleaver for deinterleaving the interleaved code words.
In another aspect of the present invention a forward error correction method is provided including encoding a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, transmitting the code words from a transmitting modem to a receiving modem, detecting any errors in any of the transmitted code words, predicting from any of the errors in the primary code word at least one error in the secondary code word, and reporting any of the predicted errors as erasure positions.
In another aspect of the present invention the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the transmitting step includes demultiplexing the code words into a plurality of code word portions, transmitting the portions via a plurality of transmitting modems, receiving the portions via a plurality of receiving modems, and multiplexing the plurality of portions, thereby reconstructing the code word.
In another aspect of the present invention the method further includes interleaving the code words prior to the transmitting step, and deinterleaving the interleaved code words subsequent to the transmitting step.
In another aspect of the present invention the method further includes configuring the decoder for decoding either of the primary and the secondary code words.
In another aspect of the present invention a forward error correction method is provided including encoding a data stream into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, demultiplexing each of the code words into a plurality of portions, transmitting a different one of the plurality of portions via a plurality of transmitting modems, receiving a different one of the plurality of portions via a plurality of receiving modems, multiplexing the plurality of portions, thereby reconstructing the code words, detecting any errors in any of the primary code words at a primary decoder, predicting from any of the errors in the primary code word at least one error in the secondary code word, reporting any of the predicted errors as erasure positions to a secondary decoder, and correcting any of the erasures in the secondary code words at the secondary encoder.
In another aspect of the present invention the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the predicting step includes predicting after determining that the number of errors detected in any of the portions exceeds a predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the method further includes interleaving the code words prior to the demultiplexing step, and deinterleaving the interleaved code words subsequent to the multiplexing step.
In another aspect of the present invention a forward error correction method is provided including encoding a data stream into at least one code word at a first code rate, demultiplexing each of the code words into a plurality of portions, transmitting a different one of the plurality of portions via a plurality of transmitting modems, receiving a different one of the plurality of portions via a plurality of receiving modems, multiplexing the plurality of portions, thereby reconstructing the code words, determining the function status of any of the modems, and where any of the modems is functioning improperly, decoding as erasures the portion transmitted by the improperly functioning modem.
In another aspect of the present invention a forward error correction method is provided including firstly encoding a data stream into at least one outer code word, secondly encoding the outer code word into at least one inner code word using either of an error correcting code and an error checking code, transmitting the inner code word, receive the transmitted inner code word, determining the validity of the transmitted inner code word, firstly decoding the inner code word, thereby reconstituting the outer code word, mapping the inner code word to its corresponding position in the reconstituted outer code word, and where the inner code word is invalid, secondly decoding the reconstituted outer code word where the position is treated as an erasure position.
In another aspect of the present invention the firstly coding step includes coding using Reed-Solomon coding and the secondly decoding step includes decoding using Reed-Solomon decoding.
In another aspect of the present invention the secondly coding step includes coding using Trellis Coded Modulation coding and the firstly decoding step includes decoding using Trellis Coded Modulation decoding.
In another aspect of the present invention the secondly coding step includes coding using Cyclic Redundancy Check coding and the firstly decoding step includes decoding using Cyclic Redundancy Check decoding.
In another aspect of the present invention in a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, a forward error correction system is provided including a decoder operative to receive the code words, detect errors in any of the code words, correct any of the errors and erasures in the code words, and communicate the positions of any of the errors, and a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions to the decoder.
In another aspect of the present invention the system further includes a coder operative to encode the data stream.
In another aspect of the present invention the system further includes at least one transmitting modem for receiving the code words ultimately from the coder and transmitting the code words, and at least one receiving modem for receiving the code words from the at least one transmitting modem and for providing the code words ultimately to the decoder.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the at least one transmitting modem includes a plurality of transmitting modems and the system further includes a demultiplexer intermediate the coder and the transmitting modems for demultiplexing the code words, thereby causing each of the transmitting modems to transit a different portion of each of the code words.
In another aspect of the present invention the at least one receiving modem includes a plurality of receiving modems for receiving the different portions of each of the code words and the system further includes a multiplexer intermediate the receiving modems and the decoder for multiplexing the portions, thereby reconstructing the code words.
In another aspect of the present invention the controller is operative to predict after determining the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the system further includes an interleaver intermediate the coder and the at least one transmitting modem for interleaving the code words, and a deinterleaver intermediate the at least one receiving modem and the decoder for deinterleaving the interleaved code words.
In another aspect of the present invention the controller is operative to send a configuration signal to the decoder configuring the decoder for decoding either of the primary and the secondary code words.
In another aspect of the present invention in a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, a forward error correction system is provided including a primary decoder operative to receive the primary code words, detect any errors in any of the primary code words, correct any of the errors, and communicate the positions of any of the errors, a controller operative to receive the communication of the error positions, predict from any of the errors in the primary code word at least one error in the secondary code word, and report any of the predicted errors as erasure positions, and a secondary decoder operative to receive the report of erasure positions and correct any of the erasures in the secondary code words.
In another aspect of the present invention the system further includes a coder operative to encode the data stream.
In another aspect of the present invention the system further includes at least one transmitting modem for receiving the code words ultimately from the coder and transmitting the code words, and at least one receiving modem for receiving the code words from the at least one transmitting modem and for providing the code words ultimately to either of the decoders.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the at least one transmitting modem includes a plurality of transmitting modems and the system further includes a demultiplexer intermediate the coder and the transmitting modems for demultiplexing the code words, thereby causing each of the transmitting modems to transmit a different portion of each of the code words.
In another aspect of the present invention the at least one receiving modem includes a plurality of receiving modems for receiving the different portions of each of the code words and the system further includes a multiplexer intermediate the receiving modems and the decoders for multiplexing the portions, thereby reconstructing the code words.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the system further includes an interleaver intermediate the coder and the at least one transmitting modem for interleaving the code words, and a deinterleaver intermediate the at least one receiving modem and the decoders for deinterleaving the interleaved code words.
In another aspect of the present invention in a communications system including a data stream encoded into at least one code word at a first code rate, the code word transmitted in a plurality of portions, a forward error correction system is provided including a plurality of receiving modems for receiving the plurality of portions, where any of the modems is operative to determine its function status and transmit a signal indicating the status, a multiplexer for multiplexing the plurality of portions, thereby reconstructing the code word, a decoder operative to detect any errors in the code word, correct any of the errors, and correct erasures, and a controller operative to receive the signal and, where the signal indicates that any of the modems is functioning improperly, report erasure positions corresponding to the portion transmitted by the improperly functioning modem to the decoder, where the decoder is operative to receive the report of erasure positions and correct any of the erasures in any of the code words.
In another aspect of the present invention the system further includes a coder operative to encode the data stream.
In another aspect of the present invention the controller is operative to instruct either of the encoder and the decoder to encode at a second code rate having a sufficient redundancy to accommodate the number of the errors and erasures.
In another aspect of the present invention the system further includes at least one transmitting modem for receiving the code words ultimately from the coder and transmitting the code words.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the at least one transmitting modem includes a plurality of transmitting modems and the system further includes a demultiplexer intermediate the coder and the transmitting modems for demultiplexing the code words, thereby causing each of the transmitting modems to transmit a different portion of each of the code words.
In another aspect of the present invention the controller is operative to predict after determining that the number of errors detected in any of the portions exceeds the predetermined error threshold, and any of the predicted errors corresponds to the portion exceeding the predetermined error threshold.
In another aspect of the present invention the system further includes an interleaver intermediate the coder and the at least one transmitting modem for interleaving the code words, and a deinterleaver intermediate the at least one receiving modem and the decoder for deinterleaving the interleaved code words.
In another aspect of the present invention in a communications system including a data stream encoded into at least one outer code word, where the at least one outer code word is further encoded into at least one inner code word using either of an error correcting code and an error checking code, a forward error correction system is provided including an inner decoder operative to receive the inner code word, determine the validity of the inner code word, communicate the validity of the inner code word, and decode the inner code word, thereby reconstituting the outer code word, a controller operative to receive from the inner coder the communication of validity of the inner code word, map the inner code word to its corresponding position in the reconstituted outer code word, and, where the inner code word is invalid, and report the position as an erasure position, and an outer decoder operative to receive the reconstituted outer code word from the inner decoder and the erasure positions from the inner decoder, detect errors in the reconstituted outer code word, and correct any of the errors and erasures in the reconstituted outer code word.
In another aspect of the present invention the system further includes an outer coder operative to encode the data stream into the at least one outer code word, an inner coder operative to encode the outer code word into the at least one inner code word, and a communications channel for transmitting the inner code word to the inner decoder.
In another aspect of the present invention in a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each seconday code word is encoded at a second code rate that is greater than the first code rate, a forward error correction method is provided including detecting any errors in any of the transmitted code words, predicting from any of the errors in the primary code word at least one error in the secondary code word, and correcting any of the predicted errors as erasure positions in any of the secondary code words.
In another aspect of the present invention the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the method further includes coding the data stream at a coder, demultiplexing the code words into a plurality of code word portions, transmitting the portions via a plurality of transmitting modems, receiving the portions via a plurality of receiving modems, and multiplexing the plurality of portions, thereby reconstructing the code word.
In another aspect of the present invention the method further includes interleaving the code words prior to the transmitting step, and deinterleaving the interleaved code words subsequent to the transmitting step.
In another aspect of the present invention the method further includes configuring the decoder for decoding either of the primary and the secondary code words.
In another aspect of the present invention in a communications system including a data stream encoded into at least one primary code word and at least one secondary code word, where each primary code word is encoded at a first code rate, and each secondary code word is encoded at a second code rate that is greater than the first code rate, a forward error correction method is provided including detecting any errors in any of the primary code words at a primary decoder, predicting from any of the errors in the primary code word at least one error in the secondary code word, and correcting any of the predicted errors as erasures in the secondary code words at a secondary encoder.
In another aspect of the present invention the predicting step includes predicting after determining that the number of errors detected in the primary code word exceeds a predetermined error threshold.
In another aspect of the present invention the method further includes coding the data stream at a coder, demultiplexing the code words into a plurality of code word portions, transmitting the portions via a plurality of transmitting modems, receiving the portions via a plurality of receiving modems, and multiplexing the plurality of portions, thereby reconstructing the code word.
In another aspect of the present invention the method further includes interleaving the code words prior to the transmitting step, and deinterleaving the interleaved code words subsequent to the transmitting step.
In another aspect of the present invention in a communications system including a data stream encoded into at least one code word at a first code rate, the code word transmitted in a plurality of portions, a forward error correction method is provided including receiving a different one of the plurality of portions via a plurality of receiving modems, multiplexing the plurality of portions, thereby reconstructing the code words, determining the function status of any of the modems, and where any of the modems is functioning improperly, correcting as erasures the portion transmitted by the improperly functioning modem.
In another aspect of the present invention in a communications method including a data stream encoded into at least one outer code word, where the at least one outer code word is further encoded into at least one inner code word using either of an error correcting code and an error checking code, a forward error correction method is provided including determining the validity of the transmitted inner code word, firstly decoding the inner code word, thereby reconstituting the outer code word, mapping the inner code word to its corresponding position in the reconstituted outer code word, and where the inner code word is invalid, secondly decoding the reconstituted outer code word where the position is treated as an erasure position.
In another aspect of the present invention the method further includes firstly coding using Reed-Solomon coding and where the secondly decoding step includes decoding using Reed-Solomon decoding.
In another aspect of the present invention the secondly coding step includes coding using Trellis Coded Modulation coding and the firstly decoding step includes decoding using Trellis Coded Modulation decoding.
In another aspect of the present invention the secondly coding step includes coding using Cyclic Redundancy Check coding and the firstly decoding step includes decoding using Cyclic Redundancy Check decoding.
It is appreciated throughout the specification and claims that references to code words having a data portion and a redundancy portion may be understood as either referring to distinct data and redundancy portions common to systematic coding techniques, or indistinct, co-mingled portions common to non-systematic and convolutional coding techniques. It is further appreciated throughout the specification and claims that references to elements of the invention xe2x80x9creportingxe2x80x9d information to other elements of the invention refers to the providing of information through notifications, indications, signals, or any other suitable communication technique known in the art.
The disclosures of all patents, patent applications, and other publications mentioned in this specification and of the patents, patent applications, and other publications cited therein are hereby incorporated by reference.